import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/6 8:22
 * @description TreeMap + O(n)查询，总时间复杂度 O(n^2)
 */
public class Solution {
    public static void main(String[] args) {

    }

}

class MyCalendarThree {
    // 差分思想
//    private TreeMap<Integer, Integer> cnt;
//    public MyCalendarThree() {
//        cnt = new TreeMap<>();
//    }
//
//    public int book(int start, int end) {
//        int ans = 0;
//        int maxBook = 0;
//        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
//        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
//        for (Map.Entry<Integer, Integer> entry: cnt.entrySet()) {
//            int freq = entry.getValue();
//            maxBook += freq;
//            ans = Math.max(ans, maxBook);
//        }
//        return ans;
//    }

    /**
     * 线段树 + 动态开点
     */
    private Map<Integer, Integer> tree;
    private Map<Integer, Integer> lazy;

    public MyCalendarThree() {
        tree = new HashMap<Integer, Integer>();
        lazy = new HashMap<Integer, Integer>();
    }

    public int book(int start, int end) {
        // 线段树
        update(start, end - 1, 0, 1000000000, 1);
        return tree.getOrDefault(1, 0);
    }

    public void update(int start, int end, int l, int r, int idx) {
        if (r < start || end < l) {
            return;
        }
        if (start <= l && r <= end) {
            tree.put(idx, tree.getOrDefault(idx, 0) + 1);
            lazy.put(idx, lazy.getOrDefault(idx, 0) + 1);
        } else {
            int mid = (l + r) >> 1;
            update(start, end, l, mid, 2 * idx);
            update(start, end, mid + 1, r, 2 * idx + 1);
            tree.put(idx, lazy.getOrDefault(idx, 0) +
                    Math.max(tree.getOrDefault(2 * idx, 0), tree.getOrDefault(2 * idx + 1, 0)));
        }
    }

}